package Matrix;

import java.util.Arrays;

/**
 * @Classname JZ04二维数组的查找
 * 在一个 n * m 的二维数组中，每一行都按照从左到右非递减的顺序排序，每一列都按照从上到下非递减的顺序排序。
 * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * @Description
 * @Date 2022/12/5 18:25
 * @Created by xjl
 */
public class JZ04二维数组的查找 {

    /**
     * @description 最简单的就是二维的遍历 时间n^2
     * @param: matrix
     * @param: target
     * @date: 2022/12/5 18:31
     * @return: boolean
     * @author: xjl
     */
    public boolean findNumberIn2DArray1(int[][] matrix, int target) {
        for (int[] nums : matrix) {
            for (int i : nums) {
                if (i == target) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * @description 利用的是遍历每一行 然后在每一行中使用二分法来判断实现
     * @param: matrix
     * @param: target
     * @date: 2022/12/6 8:10
     * @return: boolean
     * @author: xjl
     */
    public boolean findNumberIn2DArray2(int[][] matrix, int target) {
        for (int[] nums : matrix) {
            // 利用二分法来实现
            if (Arrays.binarySearch(nums, target) >= 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * @description 二分法实现
     * @param: a
     * @param: key
     * @date: 2022/12/6 8:17
     * @return: int
     * @author: xjl
     */
    private int Search(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];
            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid; // key found}
            }
        }
        return -(low + 1);  // key not found.
    }

    /**
     * @description 利用的整个函数的二分法来实现
     * @param: matrix
     * @param: target
     * @date: 2022/12/6 8:11
     * @return: boolean
     * @author: xjl
     */
    public boolean findNumberIn2DArray3(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) {
                i--;
            } else if (matrix[i][j] < target) {
                j++;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * @description 利用的方式和第三中的思想是一样的，就是将整个数组看做为一个，视为二分法来实现。
     * @param: matrix
     * @param: target
     * @date: 2022/12/6 8:45
     * @return: boolean
     * @author: xjl
     */
    public boolean findNumberIn2DArray4(int[][] matrix, int target) {
        if (matrix.length <= 0) {
            return false;
        }
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] > target) {
                j--;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }
}
